/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package Search;

/**
 *
 * @author Медведь
 */
public class salesman {
    int I=0,J=0;
int[] a;
double H=0;
int k=0;

//Основная функция
    public int[] salesman(double[][] salesman) {

        a=new int[salesman.length];
        int[] b=Salesman(salesman, H, a);
        return b;
    }
 //Функция которая просчитывает значения
    public int[] Salesman(double[][] mat,double H,int[] a){
    int n=mat.length;
    double[][] matrix=new double[n][n];
    double[][] matrix1=new double[n][n];
    double[][] matrix2=new double[n][n];
       for(int i=0;i<n;i++)
           for(int j=0;j<n;j++)
               matrix[i][j]=mat[i][j];

    plus();

    double h=privedenie(matrix);
    H+=h;
    min_cena(matrix, I, J);
    matrix1=zamena(matrix,I,J);
    matrix2=zamena2(matrix,I,J);
    if(privedenie(matrix2)>privedenie(matrix1)){
    setAI(I, J);
    System.out.println((I+1)+"->"+(J+1));//Для вывода пути
    if(k!=n)
    return Salesman(matrix1,H,a);
    else return a;
    }
         else
    {
        setAI(J, I);
        System.out.println((J+1)+"->"+(I+1));//Для вывода пути
         if(k!=n)
         return Salesman(matrix2,H,a);
        else return a;
        }
         }
//Функция, которая нужна для замены в матрице I и J столбца на бесконечность
    private double[][] zamena(double[][] mat,int I,int J){
        int n=mat.length;
        double[][] matrix=new double[n][n];
        for(int i=0;i<n;i++)
           for(int j=0;j<n;j++)
               matrix[i][j]=mat[i][j];
          for(int i=0;i<n;i++){
            matrix[I][i]=Double.MAX_VALUE;
            matrix[i][J]=Double.MAX_VALUE;
        }
        matrix[J][I]=Double.MAX_VALUE;
        return matrix;
    }
//Функция, которая заменяет [I][J] элемент на бесконечность
        private double[][] zamena2(double[][] mat,int I,int J){
        int n=mat.length;
        double[][] matrix=new double[n][n];
        for(int i=0;i<n;i++)
           for(int j=0;j<n;j++)
               matrix[i][j]=mat[i][j];
        matrix[I][J]=Double.MAX_VALUE;
        return matrix;
    }
//Функция, которая находит минимальную цену 0
    private void min_cena(double[][] mat,int I,int J){
        double min_cena=Double.MIN_VALUE;
        int n=mat.length;
        double cena;
        for(int i=0; i<n;i++)
        for(int j=0; j<n; j++)
            if(mat[i][j]==0){
                cena=cena(mat,i,j);
                if(cena>min_cena){
                    min_cena=cena;
                setI(i);
                setJ(j);}
            }
}
//Функция, которая находит цену [X][Y] элемента
    private double cena(double[][] mat,int X,int Y){
        double min_X=Double.MAX_VALUE;
        double min_Y=Double.MAX_VALUE;

        for(int i=0;i<mat.length;i++)
        if((mat[X][i]<min_X)&&(i!=Y))
            min_X=mat[X][i];

        for(int i=0;i<mat.length;i++)
        if((mat[i][Y]<min_Y)&&(i!=X))
            min_Y=mat[i][Y];

        return (min_X+min_Y);
    }
//Функция, которая приводит матрицу, и возвращает значение приведения
    private double privedenie(double[][] mat){
         int n=mat.length;
        double[][] matrix=new double[n][n];
        for(int i=0;i<n;i++)
           for(int j=0;j<n;j++)
               matrix[i][j]=mat[i][j];
                double di[]=new double[n];
        double dj[]=new double[n];
        double h=0;

        for(int i=0; i<n;i++){
        di[i]=Double.MAX_VALUE;
        for(int j=0; j<n; j++)
        if(matrix[i][j]<di[i])
            di[i]=matrix[i][j];
            }

        for(int i=0; i<n;i++)
        for(int j=0; j<n; j++)
            if(matrix[i][j]!=Double.MAX_VALUE)
                  if(di[i]!=Double.MAX_VALUE)
                    matrix[i][j]-=di[i];


        for(int j=0; j<n;j++){
        dj[j]=Double.MAX_VALUE;
        for(int i=0; i<n; i++)
        if(matrix[i][j]<dj[j])
            dj[j]=matrix[i][j];
            }

        for(int i=0; i<n;i++)
        for(int j=0; j<n; j++){
            if(matrix[i][j]!=Double.MAX_VALUE)
            {
              if(dj[j]!=Double.MAX_VALUE)
                    matrix[i][j]-=dj[j];
            }
        }
        for(int i=0; i<n;i++){
            if(di[i]!=Double.MAX_VALUE)
                h+=di[i];
            if(dj[i]!=Double.MAX_VALUE)
                h+=dj[i];
        }
        for(int i=0;i<n;i++)
           for(int j=0;j<n;j++)
               mat[i][j]=matrix[i][j];
        for(int i=0;i<n;i++)
         if(di[i]!=Double.MAX_VALUE)
        return h;
        return 0;
    }

//Функция, которая меняет значение I на x
public void setI(int x)
{
I=x;
}
//Функция, которая меняет значение J на x
public void setJ(int x)
{
J=x;
}
//Функция, которая меняет значение a[I] элемента на x
public void setAI(int i,int x)
{
a[i]=x;
}
//Функция, которая прибавляет к значению k единицу
public void plus()
{
k++;
}
}
